//https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=13&tqId=23282&ru=%2Fpractice%2F57aa0bab91884a10b5136ca2c087f8ff&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
//问题：1.重建二叉树！2.std::vector<int>::different_type使用；
//思路：1.先在找到pre数组中，找到根节点；2.找到根节点把数组切割成左子树与右子树的子数组；3.执行递归；

#include <algorithm>
#include <climits>
#include <queue>
#include <vector>

using namespace std;

struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

#include <cstddef>
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        //每个遍历都不能为0
        if(pre.size() == 0 || vin.size() == 0)
            return nullptr;
        //构建根节点
        TreeNode *root_ptr = new TreeNode(*pre.begin());

        auto vin_target_ptr = std::find(vin.begin(),vin.end(),*pre.begin());
        if (vin_target_ptr == vin.end()) return root_ptr;

        vector<int>::difference_type diff = vin_target_ptr - vin.begin() ;

        vector<int> leftpre(pre.begin() + 1, pre.begin() + diff + 1); 
        vector<int> leftvin(vin.begin(), vin.begin() + diff);
        root_ptr->left = reConstructBinaryTree(leftpre, leftvin);

        vector<int> rightpre(pre.begin() + diff + 1, pre.end());
        vector<int> rightvin(vin.begin() + diff + 1, vin.end());
        root_ptr->right = reConstructBinaryTree(rightpre, rightvin);

        return root_ptr;
    }
};